package algorithm.structure.tree.util;

import algorithm.structure.tree.b.BTreeNodeSYT;
import algorithm.structure.tree.b.BTreeSYT;
import algorithm.structure.tree.br.BRNodeSYT;
import algorithm.structure.tree.br.BRTreeSyt;
import algorithm.structure.tree.inter.BaseNodeSYT;
import algorithm.structure.tree.inter.BaseTreeSYT;

public class TreeTool {
	private static TreeTool treeTool = new TreeTool();
	private int id = 0;
	private TreeTool(){
		
	}
	public static TreeTool getInstanse(){
		return treeTool;
	}
	public String getTreeXml(BaseTreeSYT tree){
		String result= "<?xml version='1.0' encoding='iso-8859-1'?>" + 
		 "<tree id=\"0\">";
		StringBuilder s = new StringBuilder();
		generatorString(s,0,tree.getRoot(),"");
		result = result + s.toString();
		result = result +  "</tree>";
		return result;
	}
	public String getBRTreeXml(BRTreeSyt tree){
		String result= "<?xml version='1.0' encoding='iso-8859-1'?>" + 
		 "<tree id=\"0\">";
		StringBuilder s = new StringBuilder();
		generatorStringWithSize(s,0,tree.getRoot(),"");
		result = result + s.toString();
		result = result +  "</tree>";
		return result;
	}
	public String getBTreeXml(BTreeSYT tree){
		String result= "<?xml version='1.0' encoding='iso-8859-1'?>" + 
		 "<tree id=\"0\">";
		StringBuilder s = new StringBuilder();
		generatorStringWithBTree(s,tree.getRoot());
		result = result + s.toString();
		result = result +  "</tree>";
		return result;
	}
	
	
	private void generatorStringWithBTree(StringBuilder s,BTreeNodeSYT n){
		String value = "";
		if(n == null){
			//s.append("<item text=\"" + gap + "null_parent:" + value + "\" id = \"" + id++ + "\"/> \n");
			return;
		}
		for(int i =1;i<=n.getN();i++){
			value = value + n.getKey(i) + " ";
		}
		s.append("<item text=\"" + value +  "\" id = \"" + id++ + "\">\n");
		for(int i =1;i<=n.getN() + 1;i++){
			generatorStringWithBTree(s,n.getChildren(i));
		}
		s.append("</item>\n");
	}
	
	
	
	private void generatorString(StringBuilder s, int index,BaseNodeSYT n, String gap){
		String value = "";
		if(n== null || n.isNil()){
			if(n.getParent() != null && n.getParent().getNodeKey() != null){
				value = n.getParent().getNodeKey().getValue() +"";
			}
			s.append("<item text=\"" + gap + "null_parent:" + value + "\" id = \"" + id++ + "\"/> \n");
			return;
		}
		if(n.getParent() != null && n.getParent().getNodeKey() != null){
			value = n.getParent().getNodeKey().getValue() +"";
		}
		s.append("<item text=\"" + gap + n.getNodeKey().getValue()  + "_parent:" + value +  "\" id = \"" + id++ + "\">\n");
		generatorString(s,index + 1,n.getRightChild(),"(R)");
		generatorString(s,index + 1,n.getLeftChild(),"(L)");
		s.append("</item>\n");
	}
	
	private void generatorStringWithSize(StringBuilder s, int index,BRNodeSYT n, String gap){
		String value = "";
		if(n== null || n.isNil()){
			value = n.getSize()+"";
			s.append("<item text=\"" + gap + "null_size:" + value + "\" id = \"" + id++ + "\"/> \n");
			return;
		}
		value = n.getSize()+"";
		s.append("<item text=\"" + gap + n.getNodeKey().getValue()  + "_size:" + value +  "\" id = \"" + id++ + "\">\n");
		generatorStringWithSize(s,index + 1,n.getRightChild(),"(R)");
		generatorStringWithSize(s,index + 1,n.getLeftChild(),"(L)");
		s.append("</item>\n");
	}
	
	public BRNodeSYT OSSelect(BRNodeSYT x,int i){
		if(x.isNil()){
			return null;
		}
		int r = x.getLeftChild().getSize() + 1;
		if(i == r){
			return x;
		}else if(i < r){
			return OSSelect(x.getLeftChild(),i);
		}else{
			return OSSelect(x.getRightChild(),i - r);
		}
	}
	
	public int OsRank(BRTreeSyt tree,int x){
		BRNodeSYT xNode = tree.search(x);
		if(xNode!=null){
			int r = xNode.getLeftChild().getSize() + 1;
			BRNodeSYT y = xNode;
			while(y != tree.getRoot()){
				if(y == y.getParent().getRightChild()){
					r = r + y.getParent().getLeftChild().getSize() + 1;  
				}
				y = y.getParent();
			}
			return r;
		}else{
			return -1;
		}
	}
}
